package com.example;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author loubobooo
 * @Description #18. 四数之和
 * @Date 2022/3/28
 */
public class FourSum {

    /**
     * @return
     * @Author loubobooo
     * @Description 给定一个包含n 个整数的数组nums和一个目标值target，判断nums中是否存在四个元素 a，b，c和 d，使得a + b + c + d的值与target相等？找出所有满足条件且不重复的四元组。
     * 注意：
     * 答案中不可以包含重复的四元组。
     * @Date 2022/3/28
     * @Param
     **/
    public List<List<Integer>> fourSum(int[] nums, int target) {
        /**
         *  四数之和与前面三数之和的思路几乎是一样的
         *  如果前面的三数之和会做了的话，这里其实就是在前面的基础上多添加一个遍历的指针而已。
         *  会做三数之和的可以不用看下面的了。。
         *
         *  使用四个指针(a<b<c<d)。固定最小的a和b在左边，c=b+1,d=_size-1 移动两个指针包夹求解。
         *  保存使得nums[a]+nums[b]+nums[c]+nums[d]==target的解。偏大时d左移，偏小时c右移。c和d相
         *  遇时，表示以当前的a和b为最小值的解已经全部求得。b++,进入下一轮循环b循环，当b循环结束后。
         *  a++，进入下一轮a循环。 即(a在最外层循环，里面嵌套b循环，再嵌套双指针c,d包夹求解)。
         */
        List<List<Integer>> lists = new ArrayList<>();
        int length = nums.length;
        if (nums == null || length < 4) {
            return lists;
        }
        Arrays.sort(nums);

        for (int i = 0; i < length; i++) {
            // 去重
            if(i > 0 && nums[i - 1] == nums[i]){
                continue;
            }
            for (int j = i + 1; j < length; j++) {
                // 这里要注意：去重[2,2,2,2,2],target =8的情况，保证第一次能往下走
                if(j > i + 1 && nums[j - 1] == nums[j]){
                    continue;
                }
                int left = j + 1;
                int right = length - 1;
                while(left < right){
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if(sum > target){
                        right--;
                    }else if(sum < target){
                        left++;
                    }else{
                        lists.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                        if(left < right && nums[right] == nums[right - 1]){
                            right--;
                        }
                        // 第三次去重，这里用while直接找到不相等的那个索引小标
                        while(left < right && nums[left] == nums[left +1]){
                            left++;
                        }
                        left++;
                        right--;
                    }
                }
            }
        }
        return lists;
    }


    public static void main(String[] args) {
        int[] nums = {2,2,2,2,2};
        FourSum fourSum = new FourSum();
        List<List<Integer>> list = fourSum.fourSum(nums, 8);
        for (List<Integer> l : list) {
            for (Integer i : l) {
                System.out.print(i + ",");
            }
            System.out.println();
        }
    }
}
